home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 14124 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.5 KB
  1. Path: digex.net!not-for-mail
  2. From: jdc@access2.digex.net (John Cochran)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: fast find algorithm
  5. Date: 10 Apr 1996 21:56:23 -0400
  6. Organization: Express Access Online Communications, Greenbelt, MD USA
  7. Message-ID: <4khos7$fk1@access2.digex.net>
  8. References: <Dp8wE6.8DG@cix.compulink.co.uk> <4k9ggs$4ov@news1.mnsinc.com> <4kbrg8$luu@druid.borland.com> <316B2716.4993@airmail.net>
  9. NNTP-Posting-Host: access2.digex.net
  10.  
  11. In article <316B2716.4993@airmail.net>, Mark Nelson  <markn@airmail.net> wrote:
  12. >Pete Becker wrote:
  13. >> 
  14. >> In article <4k9ggs$4ov@news1.mnsinc.com>, huang@mnsinc.com says...
  15. >> >
  16. >> >Rogerio Brito (rbrito@ime.usp.br) wrote:
  17. >> >: huang@mnsinc.com (Szu-Wen Huang) wrote:
  18. >> >: >Falstaff (falstaff@xs4all.nl) wrote:
  19. >> >: >...
  20. >> >: >: Hashing is slightly slower than straight table lookup and can't be
  21. >> >: >: used when you want to delete elements from your table.
  22. >> >: >...
  23. >> >
  24. >> >: >Hashing can't be used when you want to delete elements?  Please explain.
  25. >> >
  26. >>     It depends on what you use to resolve conflicting hash values for different
  27. >> elements. If you resolve conflicts by rehashing, or by moving to the next
  28. >> available entry in the hash array, or any other mechanism that uses the array
  29. >> itself as the storage location for the conflicting value, then you can't delete
  30. >> items, cause once you do there's no way to get to the ones that used to
  31. >> conflict. The first one you try will map to your now-empty location, and it'll
  32. >> look like it wasn't found.
  33. >>     If you use a linked list at each array location to resolve conflicts then
  34. >> you can delete elements.
  35. >
  36. >Knuth gives an algorithm for deleting elements from a table when using linear probing, 
  37. >and it's pretty easy to see how that would work.  I'm not sure there is a practical 
  38. >way to remove elements when using a secondary hash probe...
  39. >
  40. >Mark Nelson
  41. >http://web2.airmail.net/markn
  42.  
  43. It's easy to do inserts or deletes in a hash table.  What you have to do is
  44. have 2 flag values for a hash entry.  Call them EMPTY and DELETED.
  45.  
  46. To insert an item into the table.
  47.    A. Generate hash
  48.    B. If table[hash] EMPTY or DELETED, then insert item into current entry
  49.       and exit
  50.    C. Rehash and repeat step B
  51.  
  52. To search for an entry in the table
  53.    A. Generate hash
  54.    B. If table[hash] EMPTY - return failure
  55.    C. If table[hash] desired entry - return success
  56.    D. Rehash and repeat step B
  57.  
  58. To delete an entry
  59.    A. Perform search for entry
  60.    B. If not found - return
  61.    C. If found, replace with DELETED
  62.  
  63.